// https://mp.weixin.qq.com/s/iJwPrTwmYHqw5z7J7rj3aA


#include <stddef.h>
#include <stdio.h>
#include <unistd.h>

#define DBG_TEACE 0
static void traverse_block(const char *content);

#define BLOCK_SIZE 40
void* first_block = NULL;


/*
Find Block
- First fit
    - best performence
    - memory fragmentation risk
- Best fit
    - best memory usage 
*/

// TODO: usage packed 属性保证sizeof s_block值的正确性 ?
typedef struct s_block *t_block; // t_block is a pointer type !!!
struct s_block {
    size_t size;   // 8B, data size
    t_block prev;  // 8B
    t_block next;  // 8B, next block
    int free;      // 4B, free flag
    int padding;   // 4B padding 4 bytes
    void *ptr;     // 8B 
    char data[1];   // virtual, not belong to block actually
};

// TODO: static
// TODO: inline
size_t align8(size_t s) {
    if (s & 0x7) {
        return s;
    }

    return ((s >> 3) + 1) << 3;
}

#if 1
// fisrt fit
t_block find_block(t_block *last, size_t size) {
    t_block b = first_block;
    while (b && !(b->free && b->size >= size)) {
       //  *last = b // necessary ?
        b = b->next;
    }

    return b;
}
#else
    // best fit
    // TODO
#endif

t_block extend_heap(t_block last, size_t s) {
    t_block b;
    b = sbrk(0);
    if (sbrk(BLOCK_SIZE + s) == (void *) -1)
        return NULL;

    b->size = s;
    b->prev = last;
    b->next = NULL;
    b->free = 0;
    if (last) 
        last->next = b;

    return b;
}

/*
b |BLOCK|    data              |
=>
b |BLOCK| data | BLOCK  | data |
*/
void split_block(t_block b, size_t s) {
    t_block new;
    new = (t_block)(b->data + s);
    new->size = b->size - s - BLOCK_SIZE;

    new->free = 1;
    new->next = b->next;
    new->prev = b;

    b->size = s;
    b->next = new;
}

t_block merge(t_block b) {
    if (b->next && b->next->free) {
        b->size += BLOCK_SIZE + b->next->size;
        b->next = b->next->next;
        if (b->next) 
            b->next->prev = b;
    }

    return b;
}

// TODO: static inline or macro 
t_block get_block(void *p) {
    char *tmp;  
    tmp = p;
    return (t_block)(tmp - BLOCK_SIZE);
}
 
int valid_addr(void *p) {
    if(first_block && p > first_block && p < sbrk(0)) 
        return p == (get_block(p))->ptr;
    return 0;
}

void *malloc22(size_t size) {
    t_block b;
    size_t s;
    s = align8(size);

    if (!first_block) {
        b = extend_heap(NULL, s);
        first_block = b;
    } else {
        t_block last;
        last = first_block;
        b = find_block(&last, s);
        if (!b) {
            b = extend_heap(last, s);
        } else {
            // Q : why > BLOCK_SIZE + 8 ? why 8 ?
            if (b->size - s > BLOCK_SIZE + 8) 
                split_block(b, s);
            b->free = 0;
        }
    }
    if (!b)
        return NULL;
#if DBG_TEACE
    traverse_block("malloc");
#endif
    b->ptr = b->data;
    return b->data;  
}

void *calloc(size_t number, size_t size) {
    size_t *p;
    size_t total;
    total = align8(number * size);
    p = malloc22(total);
    if(p) {
        for (size_t i = 0; i < total;i += sizeof(size_t)) {
            p[i] = 0;
        }
    }
    return p;
}

void free22(void *p) {
    t_block b;
    if (valid_addr(p)) {
        b = get_block(p);
        b->free = 1;

        // merge
        if(b->prev && b->prev->free)
            b = merge(b->prev);

        if (b->next)
            merge(b);

        // free last block  
        // if b is the last one, destroy it with brk 
        // so the prev->next should be the last one
        if (!b->next) {
            if (b->prev)
                b->prev->next = NULL;
            else
                first_block = NULL;
            brk(b);
        } 
    }

#if DBG_TEACE
    traverse_block("free");
#endif
}

static void traverse_block(const char* content) {
    //printf("=> %s\n", content);
    t_block b = first_block;
    while(b) {
        printf("b%u(%u) -> ", b->size, b->free);
        b = b->next;
    }
    printf("\n");
}


void* malloc2(size_t size)
{
    return malloc22(size);
}
void  free2(void *p)
{
    free22(p);
}

